import java.util.LinkedList;
import java.util.Queue;

//地图中的最高点
//测试链接：https://leetcode.cn/problems/map-of-highest-peak/
public class HighestPeak {
    int[] dx = {-1,1,0,0};
    int[] dy = {0,0,-1,1};
    int m,n;
    public int[][] highestPeak(int[][] isWater) {
        m = isWater.length; n = isWater[0].length;

        int[][] height = new int[m][n];
        //初始为全-1
        //-1表示没有被搜寻到的位置 != -1 表示当前点的高度
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                height[i][j] = -1;
            }
        }

        Queue<int[]> q = new LinkedList<>();
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(isWater[i][j] == 1) { //表示水域
                    height[i][j] = 0;
                    q.add(new int[]{i,j});
                }
            }
        }

        while(!q.isEmpty()) {
            int[] t = q.poll();
            int a = t[0], b = t[1];
            for(int i = 0; i < 4; i++) {
                int x = a + dx[i], y = b + dy[i];
                if(x >= 0 && x < m && y >= 0 && y < n && height[x][y] == -1 ) {
                    height[x][y] = height[a][b] + 1;
                    q.add(new int[]{x,y});
                }
            }
        }

        return height;
    }
}
